/* 广度优先，搜索迷宫 */

#include<iostream>
#include<queue>
#include<thread>
#include<list>
using namespace std;

struct Position
{
	int x;
	int y;

	int lastX;
	int lastY;

	Position(int i = 0, int j = 0, int lastI = 0, int lastJ = 0)
		: x(i)
		, y(j)
		, lastX(lastI)
		, lastY(lastJ)
	{
	}
};

const int mazeRow = 10;
const int mazeCol = 10;

char maze[mazeRow][mazeCol] =
{
	{ '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' },
	{ '#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#' },
	{ '#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#' },
	{ '#', ' ', ' ', ' ', ' ', '#', '#', ' ', ' ', '#' },
	{ '#', ' ', '#', '#', '#', ' ', ' ', ' ', '#', '#' },
	{ '#', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#', '#' },
	{ '#', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', '#' },
	{ '#', '#', '#', '#', '#', ' ', '#', '#', ' ', '#' },
	{ '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'A', '#' },
	{ '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' }
};

Position tMazePath[mazeRow][mazeCol];

void ResetMaze(void)
{
	for (int i = 0; i < mazeRow; i++)
	{
		for (int j = 0; j < mazeCol; j++)
		{
			if (maze[i][j] == '*')
			{
				maze[i][j] = ' ';
			}
		}
	}
}

bool bVisited[mazeRow][mazeCol] = { false };

bool IsValidPos(int i, int j)
{
	return maze[i][j] != '#' && !bVisited[i][j];
}

void MazeWFS(int startx, int starty)
{
	int step[4][2] = {
		{0, 1},		//右
		{-1, 0},		//上
		{0, -1},	//左
		{1, 0}		//下
	};

	queue<Position> quePath;
	quePath.push(Position(startx, starty));
	tMazePath[startx][startx] = Position(startx, startx);
	bVisited[startx][startx] = true;

	while (!quePath.empty())
	{
		queue<Position> queTemp;

		//取出这一层所有的点
		while (!quePath.empty())
		{
			Position t = quePath.front();
			if (maze[t.x][t.y] == 'A')
			{
				ResetMaze();
				int x = t.x;
				int y = t.y;
				while (x != startx || y != starty)
				{
					Position lastPt = tMazePath[tMazePath[x][y].lastX][tMazePath[x][y].lastY];
					x = lastPt.x;
					y = lastPt.y;
					maze[x][y] = '*';
				}

				break;
			}
			maze[t.x][t.y] = '*';

			quePath.pop();
			queTemp.push(t);
		}

		this_thread::sleep_for(1000ms);
		system("clear");
		for (int i = 0; i < mazeRow; ++i)
		{
			for (int j = 0; j < mazeCol; ++j)
			{
				cout << maze[i][j] << " ";
			}
			cout << endl;
		}

		//找到了路径，break
		if (!quePath.empty())
		{
			break;
		}

		//扩展所有的点
		while (!queTemp.empty())
		{
			Position t = queTemp.front();
			queTemp.pop();

			for (int k = 0; k < 4; k++)
			{
				int tx = t.x + step[k][0];
				int ty = t.y + step[k][1];

				if (IsValidPos(tx, ty))
				{
					Position tValid(tx, ty, t.x, t.y);
					tMazePath[tx][ty] = tValid;
					
					quePath.push(tValid);
					bVisited[tx][ty] = true;
				}
			}
		}
	}
}

int main(void)
{
	for (int i = 0; i < mazeRow; ++i)
	{
		for (int j = 0; j < mazeCol; ++j)
		{
			cout << maze[i][j] << " ";
		}
		cout << endl;
	}

	MazeWFS(1, 1);
}
